home *** CD-ROM | disk | FTP | other *** search
/ The X-Philes (2nd Revision) / The X-Philes Number 1 (1995).iso / xphiles / hp48hor1 / hailpath.doc < prev    next >
Text File  |  1995-03-31  |  6KB  |  136 lines
  1.                  ***  MATHEMATICAL RECREATION DEPARTMENT  *** 
  2.  
  3.                    HAILSTONE PATH in HP 48 Machine Language 
  4.                                by Joseph K. Horn 
  5.  
  6. How would you like to win several thousand dollars (!) and win eternal 
  7. mathematical fame on a par with that of Pierre de Fermat?  All you have to do 
  8. is prove (or disprove) "Ulam's Conjecture", also known as the 3x+1 Problem, and 
  9. the Collatz Sequence, and the Hailstone Path, and Wondrous Numbers, and the 
  10. Syracuse Algorithm, and many more monikers too maudlin to mention. 
  11.  
  12. Every significant mathematician for the past 40 years has played with this 
  13. problem.  Several are so frustrated with it that they're offering large cash 
  14. rewards for its solution.  (I've been toying with it for over 20 years!) 
  15.  
  16. The analogy is like this.  A hailstone is born at some elevation in a storm 
  17. cloud.  Updrafts keep it aloft as it accumulates more and more ice, growing 
  18. as it rises and falls through the sky.  Soon it gets so heavy that only 
  19. violent updrafts (as are found in storm clouds) can keep it aloft, and still 
  20. the hailstone's path is unpredictable.  But eventually (obviously) it will 
  21. have grown so large and heavy that it begins an unimpeded plummet towards 
  22. the ground.  End of hailstone path.  It is plain to any reasonable person that 
  23. the actual path will be unpredicatably chaotic, but the end of the path will 
  24. always be the same. 
  25.  
  26. Some wicked soul invented a mathematical equivalent.  It is very easy to state 
  27. and play with, but difficult (!) to prove.  It goes like this: 
  28.  
  29. Pick any integer > 1.  Now DO this:  IF it's odd, THEN multiply it by 3 and add 
  30. 1, ELSE divide it by 2.  REPEAT this process over and over, UNTIL you get to 1.  
  31. Sometimes the number will rise, and sometimes it will fall (like a hailstone 
  32. caught in updrafts in a storm).  But sooner or later, everything seems to get 
  33. down to 1 (the ground).  The conjecture is that ALL integers > 1 will 
  34. eventually reach 1 by this process. 
  35.  
  36. For example, let's start with 3: 
  37.  
  38.  3 is ODD,  so multiply by 3 and add 1, which gives 10; 
  39. 10 is EVEN, so divide by 2,             which gives  5; 
  40.  5 is ODD,  so multiply by 3 and add 1, which gives 16; 
  41. 16 is EVEN, so divide by 2,             which gives  8; 
  42.  8 is EVEN, so divide by 2,             which gives  4; 
  43.  4 is EVEN, so divide by 2,             which gives  2; 
  44.  2 is EVEN, so divide by 2,             which gives  1; 
  45.  1 is GROUND LEVEL, so STOP! 
  46.  
  47. Thus the "hailstone" (3) eventually reaches "ground" after rising and falling 
  48. through the numerical sky (getting all the way up to 16!).  So Ulam's 
  49. Conjecture works for 3.  Notice that 3 travels through SEVEN different numbers 
  50. before reaching 1.  I define HAILPATH(x) to be the "hailstone path distance" of 
  51. x, so HAILPATH(3) is 7.  I like to think of the hailstone 3 as getting larger 
  52. and larger with "ice" until it gets so heavy that even the mathematical 
  53. updrafts cannot keep it from falling to the ground. 
  54.  
  55. Try 7.  It gets all the way up to 52 before finally starting to come down, and 
  56. has a HAILPATH of 16. 
  57.  
  58. But, wait a second!  Isn't it possible for a number to just keep going up and 
  59. up, and never come down?  Or a number might get caught in an infinite loop.  
  60. Why not?  Number, after all, aren't REALLY hailstones... 
  61.  
  62. If anybody can find a number which doesn't reach 1, they will win many bucks 
  63. and instant fame.  This is obviously a task that the HP 48 can easily tackle! 
  64.  
  65. Here's a simple HP 48 program (written in vanilla RPL, not optimized) for 
  66. determining the hailpath of x, which I'll name 'ULAM' after the late Stanislaw 
  67. Ulam, whose love of this conjecture was exceeded only by his bafflement with 
  68. it: 
  69.  
  70. ULAM 
  71. %%HP:T(3); 
  72. \<< 0 SWAP         @ Put an empty loop counter in level 2. 
  73.   WHILE DUP 1 >    @ Exit as soon as it gets to 1. 
  74.   REPEAT 
  75.     IF DUP 2 MOD   @ is it odd? 
  76.     THEN 3 * 1 +   @ yes? then multiply by 3 and add 1; 
  77.     ELSE 2 /       @ no? then divide by 2. 
  78.     END 
  79.   SWAP 1 + SWAP    @ Increment the loop counter. 
  80.   END DROP         @ Lose the "1" and stop. 
  81. \>> 
  82.  
  83. This program takes any integer > 1 and returns the length of its hailstone path 
  84. to 1.  If X gives an answer, then you've verified Ulam's Conjecture for that X. 
  85.  
  86. This program is a lot faster than doing it by hand!  Here are some random X's, 
  87. hailpaths, and ULAM execution times: 
  88.  
  89.         X:   HailPath:   ULAM Execution Time: 
  90.          3           7         .2 sec 
  91.          7          16         .5 sec 
  92.         25          23         .7 sec 
  93.         27         111        3.4 sec 
  94.        703         170        5.3 sec 
  95.       2463         208        6.5 sec 
  96.      26623         307        9.6 sec 
  97.   63728127         949       31.3 sec 
  98. 2610744987        1050       34.6 sec 
  99. 4890328815 -- fails due to roundoff errors! 
  100.  
  101. Although that's faster than doing it by hand, wouldn't it be nice to have a 
  102. HAILPATH function that works as fast as, say, the square root function? 
  103.  
  104. Aha, glad you asked.  On this disk is a binary file called HAILPATH that is 
  105. an optimized machine language version of the program above.  Here are sample 
  106. times (compare!): 
  107.  
  108.         X:   HailPath:   HAILPATH Execution Time: 
  109.          3           7         .024 sec 
  110.          7          16         .024 sec 
  111.         25          23         .025 sec 
  112.         27         111         .029 sec 
  113.        703         170         .032 sec 
  114.       2463         208         .034 sec 
  115.      26623         307         .039 sec 
  116.   63728127         949         .071 sec 
  117. 2610744987        1050         .076 sec 
  118. 4890328815        1131         .080 sec 
  119.  
  120. As you can see, machine code is so much faster than user code that it boggles 
  121. the mind.  That 1050 entry is almost 500 times faster!  Instead of over half a 
  122. minute, it takes less than a tenth of a second!  And it's more accurate; its 
  123. internal "hailstone" size can be up to 19 digits long. 
  124.  
  125. Here's the machine language version in hex form, for those of you who use Bill 
  126. Wickes' ->ASC program instead of downloading binary files: 
  127.  
  128. %%HP:T(1); 
  129. "D9D20E1632B9691CCD20F6000AF910A1371091371471371791537822AF1AF3B6 
  130. 7AF69FBF1B7581C832FEA72B76AFAB7582255EAF9155711913711AAF51421648 
  131. 08CBB69193632B2130DE8E" 
  132.  
  133. Have fun.  Who knows; you might become rich and famous! 
  134.  
  135. Joseph K. Horn  --  (714) 858-0920  --  Peripheral Vision, Ltd. 
  136.